МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ лабораторна робота № 4 Структура даних БІНАРНЕ ДЕРЕВО ПОШУКУ № варіанта = [( 09 ) + (ASCII–код 71 )] % 20 + 1 Варіант 1  Львів-2011 1. Мета роботи: Вивчення абстрактної структури даних "Бінарне дерево пошуку". Набуття практичних навичок побудови дерева та використання його для розв'язання прикладних задач. 2. ПОСТАНОВКА ЗАДАЧІ Побудувати бінарне дерево пошуку для послідовності чисел, що вводяться з клавіатури. Реалізувати операції додавання та вилучення вузлів з бінарного дерева пошуку. Виконати обхід дерева у заданому порядку та показати: послідовність вершин дерева при проходженні його у прямому порядку; послідовність листків дерева при проходженні його у зворотньому порядку; послідовність вузлів, що мають тільки одного нащадка при проходженні дерева у симетричному порядку. Завдання №1 Cтворити дзеркальне до заданого дерево 3. Алгоритм виконання: - зчитування чисел; - добавляння цих чисел на відповідну позицію; - обхід дерева у прямому порядку; - обхід дерева у зворотному порядку; - обхід дерева у симетричному порядку; - створення дерева, дзеркального до заданого; - виведення результатів. 4. Динаміка змін бінарного дерева:





5. Реалізація на базі масиву: Індекси 0 1 2 3 4 5 6 7 8 9 10  Data 0 9 7 14 4 8 9 15 2 6 12  Father 0 2 0 10 2 1 1 3 4 4 0  Left son 0 5 4 0 8 0 0 0 0 0 0  Right son 0 6 1 7 9 0 0 0 0 0 3   6. Проходження бінарного дерева: - пряме:
7 → 4 → 2→ 6 → 9 → 8 → 9 - симетричне:
2 → 4 → 6 → 7 → 8 → 9 → 9 - зворотне:
2 → 6 → 4 → 8 → 9 → 9 → 7 7. Результат виконання:
Висновок: на цій лабораторній роботі я вивчив абстрактну структуру даних "Бінарне дерево пошуку". Набув практичних навичок побудови дерева та використання його для розв'язання прикладних задач. Додаток #include <iostream> #include <ctime> #include <cstdlib> #include "node.h" class tree { public: tree(); ~tree(); node* head; node* curr; void generate_random_tree(int size); void symetric_direction(node* curr); void reverse_direction(node* curr); void direct_direction(node* curr); tree mirror(node* curr); }; tree::tree() { head = new node(); curr = head; } tree::~tree() { delete [] head; } void tree::generate_random_tree(int size) { int choise; curr->set_random_data(); size--; while (size != 0) { choise = rand() % 2; if (choise == 0) { curr->add_left_son(); curr = curr->left_son; curr->set_random_data(); } else { curr->add_right_son(); curr = curr->right_son; curr->set_random_data(); } size--; } } void tree::symetric_direction(node* curr) { if (curr->left_son != NULL) { symetric_direction(curr->left_son); std::cout << curr->data << " "; if (curr->right_son != NULL) symetric_direction(curr->right_son); } else { std::cout << curr->data << " "; if (curr->right_son != NULL) { symetric_direction(curr->right_son); } } } tree tree::mirror(node* curr) { tree y; if (curr->left_son != NULL) { y.head->add_left_son(curr->left_son->data); mirror(curr->left_son); if (curr->right_son != NULL) { y.head->add_left_son(curr->left_son->data); mirror(curr->right_son); } } } void tree::direct_direction(node* curr) { std::cout << curr->data << " "; if (curr->left_son != NULL) { direct_direction(curr->left_son); if (curr->right_son != NULL) direct_direction(curr->right_son); } else { if (curr->right_son != NULL) { direct_direction(curr->right_son); } } } void tree::reverse_direction(node* curr) { if (curr->left_son != NULL) { reverse_direction(curr->left_son); if (curr->right_son ...